import javafx.util.Pair;

import java.util.*;

class Solution {
    public int[] dx = {0,0,1,-1};
    public int[] dy = {1,-1,0,0};
    public int cutOffTree(List<List<Integer>> forest) {
        // 先确定都有哪些高度的树，方便砍树的时候知道找哪棵树
        int m = forest.size();
        int n = forest.get(0).size();
        PriorityQueue<Pair<int[], Integer>> heap = new PriorityQueue<>(new Comparator<Pair<int[], Integer>>(){
            public int compare(Pair<int[], Integer> p1, Pair<int[], Integer> p2){
                return p1.getValue() - p2.getValue();
            }
        });
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int tmp = forest.get(i).get(j);
                if(tmp > 1){
                    heap.offer(new Pair<int[], Integer>(new int[] {i, j}, tmp));
                }
            }
        }

        int totalStep = 0;
        int num = forest.get(0).get(0);
        Pair<int[], Integer> start = new Pair<>(new int[] {0, 0}, num);
        while(!heap.isEmpty()){
            Pair<int[], Integer> target = heap.poll();
            int step = calStep(forest, start, target);
            if(step == -1){
                return -1;
            }else{
                totalStep += step;
            }
            start = target;
        }
        return totalStep;
    }
    public int calStep(List<List<Integer>> forest, Pair<int[], Integer> start, Pair<int[], Integer> end){
        if(start.getValue().equals(end.getValue())){
            return 0;
        }
        int m = forest.size();
        int n = forest.get(0).size();
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int[] point = start.getKey();
        int[] target = end.getKey();
        queue.offer(point);
        vis[point[0]][point[1]] = true;
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            step++;
            while(size > 0){
                int[] pos = queue.poll();
                int a = pos[0];
                int b = pos[1];
                for(int i = 0; i < 4; i++){
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && forest.get(x).get(y) != 0 && !vis[x][y]){
                        //if(forest.get(x).get(y) == end.getValue()){
                        if(x == target[0] && y == target[1]){
                            return step;
                        }
                        queue.offer(new int[] {x, y});
                        vis[x][y] = true;
                    }
                }
                size--;
            }
        }
        return -1;
    }
}